package com.SuanFa.lanqiao;

public class a2 {
    //关键句子
    private static final String TARGET = "从我做起振兴中华";

    // 方向数组，表示横向和纵向移动
    private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    // 格子中的字
    private static final char[][] GRID = {
            {'从', '我', '做', '起', '振'},
            {'我', '做', '起', '振', '兴'},
            {'做', '起', '振', '兴', '中'},
            {'起', '振', '兴', '中', '华'}
    };
    // 记录路径数
    private static int count = 0;

    public static void main(String[] args) {
        dfs(0, 0, 0);
        System.out.println("总共有 " + count + " 种可能的跳跃路线。");
    }

    private static void dfs(int x, int y, int index) {
        // 如果当前字不符合目标句子的顺序，剪枝
        if (GRID[x][y] != TARGET.charAt(index)) {
            return;
        }

        // 如果到达终点且路径符合要求，计数加1
        if (index == TARGET.length() - 1) {
            count++;
            return;
        }

        // 尝试向四个方向移动
        for (int[] dir : DIRECTIONS) {
            int newX = x + dir[0];
            int newY = y + dir[1];

            // 检查新位置是否在格子范围内
            if (newX >= 0 && newX < GRID.length && newY >= 0 && newY < GRID[0].length) {
                dfs(newX, newY, index + 1);
            }
        }
    }
}

